class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        path = []
        opt = [False] * n
        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return 
            for j in range(n):
                if not opt[j] :
                    path.append(nums[j])
                    opt[j] = True
                    dfs(i+1)
                    opt[j] = False
                    path.pop()
        
        dfs(0)
        return ans

# 大佬写法
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans =[]
        path = [0] * n
        def dfs(i,s):
            if i == n:
                ans.append(path.copy())
            
            for x in s:
                path[i] = x
                dfs(i+1,s-{x})


        dfs(0,set(nums))
        return ans